package heap

import (
	"container/heap"
	"log"
)

func Init2(h heap.Interface) {
	// heapify
	n := h.Len()
	for i := n/2 - 1; i >= 0; i-- {
		siftDown(h, i, n)
	}
}

func siftUp(h heap.Interface, n int) {
	for {
		if n == 0 {
			break
		}
		if !h.Less(parent(n), n) {
			h.Swap(parent(n), n)
			n = parent(n)
		}
	}
}

func siftDown(h heap.Interface, i0, n int) {
	i := i0
	for {
		leftChildIndex := leftChild(i)
		if leftChildIndex >= n || leftChildIndex < 0 {
			break
		}
		j := leftChildIndex
		// 如果数组没有越界，并且右节点小于左子节点
		// 最主要的目的是 选择三个节点中最小的那个
		if rightChild(i) < n && h.Less(rightChild(i), leftChildIndex) {
			j = rightChild(i)
		}

		if !h.Less(j, i) {
			break
		}

		h.Swap(i, j)

		i = j

	}
}

// heap is full binary tree
func parent(idx int) int {
	if idx == 0 {
		log.Fatalf("index-0 does't have parent")
	}
	return (idx - 1) / 2
}

func leftChild(idx int) int {
	return 2*idx + 1
}

func rightChild(idx int) int {
	return 2*idx + 2
}
